package com.z.test;

import java.util.Arrays;

public class ShellSort {
    private static int[] arr = new int[]{1,4,3,5,6,2};

    // 希尔排序
    public static void shell_sort(int[] arrs){
        int[] arr = Arrays.copyOf(arrs,arrs.length);
        int len = arr.length;
        System.out.println("希尔排序 shell sort:");
        printArrs("原始：", arr);
        for(int gap = (int) Math.floor(len / 2); gap > 0; gap = (int) Math.floor(gap / 2)) {
            System.out.println("gap:"+gap);
            // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
            for(int i = gap; i < len; i++) {
                System.out.println("i:"+i);
                int j = i;
                int current = arr[i];

                System.out.println("j:"+j);
                while(j - gap >= 0 && current < arr[j - gap]) {
                    arr[j] = arr[j - gap];
                    j = j - gap;
                }

                System.out.println("j:"+j);
                arr[j] = current;
            }
        }
        printArrs("最终：" , arr);
    }

    public static void main(String[] args) {
        shell_sort(arr);
    }







    static void printArrs(String preStr , int[] arr){
        String str = "";
        for(int i=0;i<arr.length;i++){
            str += arr[i] + ",";
        }
        System.out.println(preStr + str.substring(0,str.length()-1));
    }
}
